package com.df.sort;

/**
 * 归并排序
 *
 * @author dongfang
 */
public class Merge {

    /**
     * <EM>归并排序（Merge）</EM>是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
     * <p>
     * 归并排序是建立在归并操作上的一种有效的排序算法。<br/>
     * 该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 <br/>
     * 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。<br/>
     * <p>
     * -----
     * <pre>
     * 归并排序算法稳定，
     * 数组需要O(n)的额外空间，链表需要O(log(n))的额外空间，
     * 时间复杂度为O(nlog(n))，
     * 算法不是自适应的，不需要对数据的随机读取。
     * </pre>
     *
     * @param array
     */
    public static void merge(int[] array) {
        int length = array.length;
        int[] reg = new int[length];
        int num = mergePartition(array, reg, 0, length - 1);

        System.out.println("mergeAlpha num [" + num + "]");

    }

    public static void mergeAlpha(int[] array) {
        int num = 1;
        int length = array.length;
        int[] result = new int[length];

        for (int block = 1; block < length; block *= 2) {
            for (int i = 0; i < length; i += 2 * block) {
                int low = i;
                int mid = (i + block) < length ? (i + block) : length;
                int high = (i + 2 * block) < length ? (i + 2 * block) : length;

                //两个块的起始下标及结束下标
                int stratL = low;
                int startH = mid;
                //开始对两个block进行归并排序
                while (stratL < mid && startH < high) {
                    result[low++] = array[stratL] < array[startH] ? array[stratL++] : array[startH++];
                    num++;
                }
                while (stratL < mid) {
                    result[low++] = array[stratL++];
                    num++;
                }
                while (startH < high) {
                    result[low++] = array[startH++];
                    num++;
                }
            }
            int[] temp = array;
            array = result;
            result = temp;
        }
        System.out.println("mergeAlpha num [" + num + "]");

    }


    /**
     * <EM>归并排序（英语：Merge sort，或mergesort）</EM>，是创建在归并操作上的一种有效的排序算法，效率为O(nlogn)。
     * <Pre>
     * 原理如下（假设序列共有n个元素）：
     * 1.将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素
     * 2.将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素
     * 3.重复步骤2，直到所有元素排序完毕
     * </Pre>
     *
     * @param array
     * @param reg
     * @param start
     * @param end
     */
    private static int mergePartition(int[] array, int[] reg, int start, int end) {
        if (start >= end)
            return 0;

        int num = 0;
        int mid = ((end - start) >> 1) + start;

        int startL = start;
        int startH = mid + 1;
        mergePartition(array, reg, startL, mid);
        mergePartition(array, reg, startH, end);

        int i = start;
        while (startL <= mid && startH <= end) {
            reg[i++] = array[startL] < array[startH] ? array[startL++] : array[startH++];
            num++;
        }
        while (startL <= mid) {
            reg[i++] = array[startL++];
            num++;
        }
        while (startH <= end) {
            reg[i++] = array[startH++];
            num++;
        }
        for (i = start; i <= end; i++) {
            array[i] = reg[i];
            num++;
        }

        return num;
    }
}
